package top.humbleyuan.dichotomy;

import java.util.Arrays;

/**
 * @Author: yuanhuanghui
 * @Date: 2020-08-18
 * @Time: 14:22
 * @Description: 排序数组中找第一个和最后一个target
 */
public class LeetCode_34 {
    public static void main(String[] args) {
        // 递归二分后线性搜索
        //m1();

        //
        m2();
        System.out.println();
    }

    /**
     * 二分：
     * 1. 若nums[mid] != target, 继续二分（根据大小）
     * 2. 若nums[mid] == target :
     *  2.1 若mid前后都和target相等，前后找到边界（**这里不满足logN**）
     *  2.2 若mid已经是边界则继续二分
     *  2.2 若mid是唯一target,直接判断跳出
     */
    static int[] res = {-1, -1};
    public static int[] m1() {
        int[] nums = {0,0,0,0};
        int target = 0;
        if(nums == null || nums.length == 0) {
            return res;
        }
        // 二分
        divide(nums, 0, nums.length - 1, target);

        return res;
    }

    public static void divide(int[] nums, int start, int end, int target) {
        if(start > end) {
            return;
        }
        int mid = (start + end) / 2;

        if(nums[mid] == target) {
            if(mid == nums.length - 1 || nums[mid + 1] > target) {
                res[1] = mid;
                // 唯一值
                if(mid == 0 || nums[mid - 1] < target) {
                    res[0] = mid;
                    return;
                }
                divide(nums, 0, mid - 1, target);
            }else if(mid == 0 || nums[mid - 1] < target) {
                res[0] = mid;
                divide(nums, mid + 1, end, target);
            }else {
                res[0] = mid;
                res[1] = mid;
                for (int i = 1; i <= mid + 1; i++) {
                    if(mid - i >= 0 && nums[mid - i] == target) {
                        res[0] = mid - i;
                    }

                    if(mid + i < nums.length && nums[mid + i] == target) {
                        res[1] = mid + i;
                    }
                }
            }
            return;
        }

        // 都在前半部分
        if(nums[mid] > target) {
            divide(nums, 0, mid - 1, target);
        }

        if(nums[mid] < target) {
            divide(nums, mid + 1, end, target);
        }
    }

    /**
     * 非递归二分：
     * 先找左边界，后找右边界
     */
    public static void m2() {
        int[] res = {-1, -1};
        int[] nums = {0,0,0,0, 0};
        int target = 0;

        /**
         * 左边界：
         * 注意相等时记录下当前index,继续向左逼近
         */
        int left = 0, right = nums.length - 1;

        while(left <= right) {
           int mid = left + (right - left) / 2;
           if(nums[mid] < target) {
               left = mid + 1;
           } else if(nums[mid] > target) {
               right = mid - 1;
           } else if(nums[mid] == target) {
               right = mid - 1;
               res[0] = mid;
           }
        }

        /**
         * 右边界
         */
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            } else if(nums[mid] > target) {
                right = mid - 1;
            } else if(nums[mid] == target) {
                left = mid + 1;
                res[1] = mid;
            }
        }

        System.out.println(Arrays.toString(res));


    }

}
